package sort;

import java.util.Arrays;

/**
 * @description: 计数排序
 * @title: CountingSort
 * @author: zp
 * @date: 2021/11/20 16:27
 * <p>
 * 所以我们可以建立一个长度为7的数组，下标范围为0~6就可以表示所有的需要排列的数据。
 * 我们需要做的就是遍历我们的数据如果是6就让新数组下标为6的值自加1；如果是5就让下标为5的值自加1，以此类推。
 * 随后我们遍历新数组，通过值确定输出下标的次数，来完成输出。
 * <p>
 * 遍历方式有多种
 */
public class CountingSort extends BaseSort {
    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};
        // Find the maximum element in the input array
        int max = findMaxElement(array);
        int[] sortedArr = countingSort(array, max + 1);
        System.out.println(Arrays.toString(sortedArr));
    }

    /**
     * @description: 找到数组中最大的元素
     * @author: zp
     * @date: 21:15
     * @param: array
     * @return: int
     */
    private static int findMaxElement(int[] array) {
        int max = array[0];
        for (int val : array) {
            if (val > max) {
                max = val;
            }
        }
        return max;
    }

    private static int[] countingSort(int[] array, int range) {
        int[] output = new int[array.length];
        int[] count = new int[range];

        for (int i = 0; i < array.length; i++) {
            //找到元素对应下标位置 给那个下标的值加一
            count[array[i]]++;
        }
        //计算数据 把前面数据的个数都加起来 数据对应的下标位置数值减一就是正确位置
        for (int i = 1; i < range; i++) {
            count[i] = count[i] + count[i - 1];
        }

        // 遍历数组 取出count数组里对应的数据 替换原来数组中的值
        for (int i = 0; i < array.length; i++) {
            output[count[array[i]] - 1] = array[i];
            //count计数减一 因为取出一个数
            count[array[i]]--;
        }
        return output;
    }

}
